package com.xiaoyu.dfs;

import java.util.Arrays;

/**
 * @program: DS_and_A
 * @description: 被围绕的区域
 * 给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，
 * 找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
 *
 * 输入：board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
 * 输出：[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
 * 解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的'O'都不会被填充为'X'。
 * 任何不在边界上，或不与边界上的'O'相连的'O'最终都会被填充为'X'。
 * 如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
 *
 * @author: YuWenYi
 * @create: 2021-06-04 11:29
 **/
public class SurroundedArea_130 {
    //右,上,左,下
    public static final int[][] DIRECTIONS = {{0,1},{-1,0},{0,-1},{1,0}};
    private char[][] board;
//错误解法,从内到外无法掌控其变化....所有需要从边界下手
//如果从边界下手,将会简单很多
/*    public void solve(char[][] board) {
        int row = board.length;
        int col = board[0].length;
        this.board = board;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (board[i][j] == 'O'){
                    isSurround(i,j);
                }
            }
        }
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (board[i][j] == 'V'){
                    board[i][j] = 'X';
                }
                if (board[i][j] == 'N'){
                    board[i][j] = 'O';
                }
            }
        }
    }
    public boolean isSurround(int x,int y){
        if (board[x][y] == 'X'){
            return true;
        }

        if (board[x][y] == 'O'){
            board[x][y] = 'V';  //visited
            for (int[] direction : DIRECTIONS) {
                int x1 = x + direction[0];
                int y1 = y + direction[1];
                if (inMap(x1, y1)){  //如果在地图中
                    boolean surround = isSurround(x1, y1); //那么就去递归
                    if (!surround || board[x1][y1] == 'N'){   //如果递归回来发现是false,那么即遇到了边界,那么之前的所有V都需要改成N
                        board[x][y] = 'N';
                        return false;
                    }
                }else {
                    board[x][y] = 'N';
                    return false;
                }
            }
        }
        return true;   //这里是当board[x][y] == 'V'的情况
    }*/


    public void solve(char[][] board) {
        int row = board.length;
        int col = board[0].length;
        this.board = board;
        //只对边界做dfs
        for (int i = 0; i < row; i++) {
            dfs(i, 0);  //第一列
            dfs(i, col-1); //最后一列
        }
        //第二列到倒数第二列
        for (int j = 1; j < col-1; j++) {
            dfs(0, j);   //第一行
            dfs(row-1, j);  //最后一行
        }
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (board[i][j] == 'O'){
                    board[i][j] = 'X';
                }
                if (board[i][j] == 'N'){
                    board[i][j] = 'O';
                }
            }
        }
    }

    public void dfs(int x,int y){
        if (!inMap(x, y) || board[x][y] != 'O'){
            return;
        }
        board[x][y] = 'N';
        for (int[] direction : DIRECTIONS) {
            int x1 = x + direction[0];
            int y1 = y + direction[1];
            dfs(x1, y1);
        }
    }

    private boolean inMap(int x, int y) {
        return x>=0 && x < board.length && y>=0 && y < board[0].length;
    }


    public static void main(String[] args) {
        char[][] board = {
                {'X','O','X','X'},
                {'X','O','O','X'},
                {'X','X','O','X'},
                {'X','O','X','X'}
        };
        SurroundedArea_130 surroundedArea_130 = new SurroundedArea_130();
        surroundedArea_130.solve(board);
        for (char[] chars : board) {
            System.out.println(Arrays.toString(chars));
        }
    }
}
